#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
using namespace std;

/**
对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。

  给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。
保证A中元素均为正整数。

测试样例：
[1,4,6,5,9,10],6
返回：2
  所谓最短需排序子数组是指一个需要排序的最大区域，即题目中的数组只要找到一个待排序区域而不是分离的几段，如果在一个区域中元素
逐步递增，即在遍历这个区域时，每个当前元素都是最大值max，那么说明这个区域是有序的；如果从某个元素开始，之后存在元素小于这个元素，
那么这段区域就是非有序的，是需要排序的。为什么需要保留最大值max，在遍历时要保留最大值max，如果后面的每个元素都更大，则max会逐步向
后面移动，因此max所在的区域都是有序的，如果在max后面出现了一个元素小于这个max，即没有替换这个max值，于是这个当前值到前面max所在的
区域必然是需要重新排序的，此时用int right指针记录这个位置，之后再往后面移动，如果下一个元素大于max，则重新替换max，再往下移动，
如果下一个元素小于max，则将right替换为当前值，说明这个元素之前需要重排序；一直按此进行，即只要值小于max，就应该赋值给right表示之
前的部分是无需的，直到全部遍历完成，此时right所在的位置是应该排序的区域的右端点，在right及左边元素的区域是无序的。那么需要排序的
区域的起始位置再哪里呢？应该是第一个小于max的元素对应的max所在的元素，即从某个元素开始如果元素小于了前面那么元素，说明开始无序，
于是记录第一个right的位置start即可，区域开始的位置就是start-1；由于记录开始减少的第一个元素较麻烦，可以通过逆向遍历的方式来求无
序数组的开始位置，以A[n-1]的值作为min,从i=n-2开始向前遍历元素，如果A[i]<min，那么就替换min，如果A[i]>min，说明出现了破坏数组有序性
的元素，因此将该值赋值给left，于是从left所在位置向右的区域是需要重新排序的，以此方式向左遍历数组，当遍历完成时，left所在的位置就是
需要重新排序的区域的第一个元素，于是最终[left,right]区域就是需要重新排序的区域，于是长度是right-left+1；注意理解，这里不必担心left>=right，
因为2次遍历是对同一个数组进行的，因此结果一定是唯一统一的，如果存在无序的区域，那么一定是[left,right]，如果不存在无序区域，即整个序列有序
，那么必然有left=0；并且同时right=n-1,此时待排序部分长度是0，返回0即可。时间复杂度O(n)，空间复杂度O(1)

*/

int shorestSequence(vector<int> arr , int n)
{
	int big = arr[0];
	int small = arr[n - 1];
	int p = 0;
	int q = n - 1;

	for (int i = 0 ; i < n ; i++)
	{
		//小于当前数组的值，改变下标的索引值
		if (big > arr[i])
		{
			p = i;
		}
		else
		{
			//大于等于赋值
			big = arr[i];
		}
		if (small < arr[n-i-1])
		{
			//比当前值小，改变索引
			q = n - i - 1;	
		}
		else
		{
			//大于等于，赋值
			small = arr[n - i - 1];
		}

	}
	//完全有序
	if (p == 0 && q == n-1)
	{
		return 0;
	}
	return p - q + 1;
}
int main()
{
	vector<int> v = { 1,4,6,5,9,10 };
	cout << shorestSequence(v,6)<< endl;
	getchar();
	return 0;
}